package swordoffer.offer35;

public class BestSolution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        RandomListNode cur = pHead;
        RandomListNode copyNode = null;
        //生成原链表的拷贝节点，插入位置在原节点后面
        while (cur != null) {
            RandomListNode next = cur.next;
            copyNode = new RandomListNode(cur.label);
            cur.next = copyNode;
            copyNode.next = next;
            cur = next;
        }
        cur = pHead;
        //为拷贝节点设置random指针
        while (cur != null) {
            RandomListNode next = cur.next.next;
            copyNode = cur.next;
            copyNode.random = cur.random == null ? null : cur.random.next;
            cur = next;
        }
        //保存拷贝节点的头节点
        RandomListNode res = pHead.next;
        cur = pHead;
        //为拷贝节点设置next指针。断链
        while (cur != null) {
            RandomListNode next = cur.next.next;
            copyNode = cur.next;
            copyNode.next = next == null ? null : next.next;
            cur.next = next;
            cur = next;
        }
        return res;
    }
}
